"""
线性时间选择
"""

from QuickSort import RandomizedPartiton, Partition
from MergeSort import MergeSort


# 方法一: 平均O(n),最差O(n^2)
# 筛选出数组内部第k小的元素
def RandomizedSelect(a, p, r, k):
    if p == r:
        return a[p]
    i = RandomizedPartiton(a, p, r)
    j = i - p + 1  # j等于前半段长度
    if k <= j:
        return RandomizedSelect(a, p, i, k)
    else:
        return RandomizedSelect(a, i + 1, r, k - j)


a = [3, 1, 2, 5, 9, 6, 7, 8]
x = RandomizedSelect(a, 0, len(a) - 1, len(a) - 1)
print("first way 第二大：", x)


# 方法二: 最坏情况下也能O(n)
def Select(a, p, r, k):
    if r - p < 75:
        MergeSort(a, p, r)
        return a[p + k - 1]
    else:
        for item in range((r - p - 4) // 5):  # 将其按5个一组分组从a[p+i*5]到 a[p+i*5+4]
            x = Select(a, p, p + (r - p - 4) // 5, (r - p - 4) // 10)  # 找出中位数的中位数
            i = Partition(a, p, r, x)
            j = r - p + 1
            if k < j:
                return Select(a, p, i, k)
            else:
                return Select(a, i + 1, r, k - j)


print("second way 第二大：", Select(a, 0, len(a) - 1, len(a) - 1))
